package leetcode; /**
 * description:
 * author:zt
 * date:2021-08-16
 */

import java.util.ArrayList;

/**
 * 假设有从 1 到 N 的 N 个整数，如果从这 N 个数字中成功构造出一个数组，使得数组的第 i 位 (1 <= i <= N) 满足如下两个条件中的一个，我们就称这个数组为一个优美的排列。条件：
 *
 * 第i位的数字能被i整除
 * i 能被第 i 位上的数字整除
 * 现在给定一个整数 N，请问可以构造多少个优美的排列？
 */
public class leetcode526 {
    boolean[] visited;
    int ans = 0;
    public int countArrangement(int n) {
        visited = new boolean[n+1];
        dfs(1,n,new ArrayList<>());
        return ans;
    }
    public void dfs(int index,int n,ArrayList<Integer> path){
        if (index>n){
            ans++;
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (!visited[i] && (index%i==0 || i%index==0)){
                visited[i] = true;
                path.add(i);
                dfs(index+1,n,path);
                visited[i] = false;
                path.remove(path.size()-1);
            }
        }
    }
}
